'''
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

 

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 3:
            return n

        dp = [0] * (n + 1)
        dp[1] = dp[2] = dp[3] = 1
        square_nums = [i * i for i in range(1, int(n ** 0.5) + 1)]    #[1,根号n]中的平方数

        for i in range(1, n + 1):
            tmp = []
            for num in square_nums:
                if i - num < 0:
                    break
                tmp.append(dp[i - num])
            dp[i] = min(tmp) + 1
        return dp[n]

n = 50
Solution().numSquares(n)